import java.util.TreeMap;
import java.util.Map;

public class MemoryManager
	{

	TreeMap<Integer, Area> free; // Here, the key is the value where the memory starts and the value is the area of the memory which contains the beginning, end, and size of the memory
	TreeMap<Integer, Area> used;

	public MemoryManager(int size)
		{

			free = new TreeMap<Integer, Area>();
			used = new TreeMap<Integer, Area>();
			
			free.put(0, new Area(0, size));

		}

	public Area aquire(int amount)
		{

			int key;
  			Area value, used_value, free_value;


			synchronized (free) {

				for(Map.Entry<Integer, Area> entry: free.entrySet()){
					key = entry.getKey();
  					value = entry.getValue();

					if(value.getSize()>=amount){

						free_value = new Area(value.getStart()+amount, value.getEnd());
						free.remove(value.getStart());

						free.put(value.getStart()+amount, free_value);


						if(free_value.getStart()==free_value.getEnd()){
							free.remove(free_value.getStart());
						}

						used_value = new Area(value.getStart(), value.getStart()+amount);
						used.put(value.getStart(), used_value);

						return used_value;
					}

				}

				// go through every entry in free
					// check if the block of free memory is large enough for the amount requested
						// if the block is large enough, add the requested block to the used memory TreeMap
						// since you added memory to the used block, you need to remove the same amount of memory from the free block
						// return the area object from the for loop
					// check if the start of the free block is the same as the end of the free block
						// then, remove the block from the free TreeMap
						// return null from this if statement
			}

			return null;
		}

	public void release(int startAddress)
		{

			int key, free_prev_end=-1, free_prev_start=-1;
  			Area value, free_value, new_free_value;

			synchronized (free) {

				for(Map.Entry<Integer, Area> entry: used.entrySet()){
					key = entry.getKey();
  					value = entry.getValue();

  					if(key == startAddress){

  						free_value = new Area(startAddress, value.getEnd());
  						used.remove(key);
  						free.put(key, free_value);
  						break;

  					}

  				}


  				for(Map.Entry<Integer, Area> entry: free.entrySet()){
  					key = entry.getKey();
  					value = entry.getValue();

  					if(value.getStart() == free_prev_end){

						free.remove(free_prev_start);
						free.remove(value.getStart());
						free_value = new Area(free_prev_start, value.getEnd());

						free.put(free_prev_start, free_value);

						if(free.containsKey(free_value.getEnd())){

							new_free_value = new Area(free_value.getStart(), free.get(free_value.getEnd()).getEnd());

							free.remove(free_value.getEnd());

							free.put(free_value.getStart(), new_free_value);
						}


						break;
  					}

  					free_prev_end = value.getEnd();
  					free_prev_start = value.getStart();

  				}

				// if the start address is a key in the used TreeMap
					// release the block from the used TreeMap and add this block back to the fre TreeMap
					// Here, you will need to combine free memory whenever possible
			}
		}

	public void print()
		{
			synchronized (free)
				{
					System.out.println("\nFree");
					free.forEach((k, v) -> System.out.println(k + "->" + v.getEnd() + "(" + v.getSize() + ")"));
					System.out.println("Used");
					used.forEach((k, v) -> System.out.println(k + "->" + v.getEnd() + "(" + v.getSize() + ")"));
				}
		}

	public Area getFirstFree()
		{

			return free.firstEntry().getValue();

		}

	}